package zw_1_100.zw_29_两数相除;


class Solution {

    public static void main(String[] args) {
        int dividend = 10;
        int divisor = 3;
        int n = divide(dividend, divisor);
        System.out.println(n);
    }

    /**
     * 首先, 单纯的暴力, 咱们可以很明显的想到用减肥来代替除法, 不停的用被除数减去除数, 直到被除数小于除数.
     * 如何特判负数? 根据除法的性质, 两个数同号则正, 异号则负, 因此可以通过最高位异或来判断返回结果是否是负数.
     * boolean fu = (((dividend >>> 31) ^ (divisor >>> 31)) == 1);
     * 然后就是坑点了, 如何转换使两数同号, 因为对应符号不同的两数, 除法实际上是需要加法模拟的, 为了统一用减法模拟, 需要进行符号转换,
     * 这里千万注意数据范围最小是-2147483638, 因此如果转换为正数, 会很悲惨的溢出, 所以需要转换为负数.
     *
     * 效率优化: 很明显, 对于一次次减是不可行的, 但咱们可以减除数的2倍,然后结果+2,4倍+4...... 故不停的左移除数, 直到其大于被除数的一半,
     * 然后减去, 右移除数使其小于被除数,减去......依次类推, 直到被除数小于原始除数.
     * @param dividend
     * @param divisor
     * @return
     */
    public static int divide(int dividend, int divisor) {
        boolean f = true;
        if (dividend > 0) {
            dividend = -dividend;
            f = !f;
        }
        if (divisor > 0) {
            divisor = -divisor;
            f = !f;
        }
        int result = 0;
        int n = 0;
        int compare = dividend;
        // 求出最大n的值，但是-1的右移一位仍是-1， 所以要提前终止
        while (compare <= divisor && compare != -1) {
            compare = compare >> 1;
            ++n;
        }
        // 防止越界， 比如说1 - 2^31右移31位是-2，而在下面while循环中如果-2向左移移动31位则为0，此时就会进入if语句中导致死循环
        --n;
        while (dividend <= divisor) {
            compare = divisor << n;
            // 最大的n使得divisor左移n位的绝对值不超过dividend的绝对值
            if (compare >= dividend) {
                result -= (1 << n);
                dividend -= (divisor << n);
            }
            --n;
        }
        return f ? (result == Integer.MIN_VALUE ? Integer.MAX_VALUE : -result) : result;
    }


//    public static int divide(int dividend, int divisor) {
//        // 考虑被除数为最小值的情况
//        if (dividend == Integer.MIN_VALUE) {
//            if (divisor == 1) {
//                return Integer.MIN_VALUE;
//            }
//            if (divisor == -1) {
//                return Integer.MAX_VALUE;
//            }
//        }
//        // 考虑除数为最小值的情况
//        if (divisor == Integer.MIN_VALUE) {
//            return dividend == Integer.MIN_VALUE ? 1 : 0;
//        }
//        // 考虑被除数为 0 的情况
//        if (dividend == 0) {
//            return 0;
//        }
//
//        // 一般情况，使用二分查找
//        // 将所有的正数取相反数，这样就只需要考虑一种情况
//        boolean rev = false;
//        if (dividend > 0) {
//            dividend = -dividend;
//            rev = !rev;
//        }
//        if (divisor > 0) {
//            divisor = -divisor;
//            rev = !rev;
//        }
//
//        int left = 1, right = Integer.MAX_VALUE, ans = 0;
//        while (left <= right) {
//            // 注意溢出，并且不能使用除法
//            int mid = left + ((right - left) >> 1);
//            boolean check = quickAdd(divisor, mid, dividend);
//            if (check) {
//                ans = mid;
//                // 注意溢出
//                if (mid == Integer.MAX_VALUE) {
//                    break;
//                }
//                left = mid + 1;
//            } else {
//                right = mid - 1;
//            }
//        }
//        return rev ? -ans : ans;
//
//
//    }
//    // 快速乘
//    public static boolean quickAdd(int y, int z, int x) {
//        // x 和 y 是负数，z 是正数
//        // 需要判断 z * y >= x 是否成立
//        int result = 0, add = y;
//        while (z != 0) {
//            if ((z & 1) != 0) {
//                // 需要保证 result + add >= x
//                if (result < x - add) {
//                    return false;
//                }
//                result += add;
//            }
//            if (z != 1) {
//                // 需要保证 add + add >= x
//                if (add < x - add) {
//                    return false;
//                }
//                add += add;
//            }
//            // 不能使用除法
//            z >>= 1;
//        }
//        return true;
//    }
}


